16.5 KB · ⇊ 11 parts · ⤓ Micron 16.5 KB · ⤓ HTML 74.3 KB

top

En algèbre et en cryptologie, une matrice MDS est une matrice possédant des propriétés particulières liées aux codes optimauxcite-ref-1[1]. Les propriétés de ces matrices sont particulières et bien connues, ce qui participe notamment à l'analyse des algorithmes de chiffrement par bloc qui les utilisent. Plus précisément, dans une série d'articles scientifiques portant sur les propriétés des réseaux de substitution-permutation, Heys et Tavarescite-ref-2[2]cite-ref-3[3] ont montré que remplacer la couche de permutation par une couche linéaire de diffusion améliorait la résistance aux attaques cryptanalytiques, notamment la cryptanalyse linéaire et différentiellecite-ref-4[4]. Pour cette raison, le terme de « matrice de diffusion MDS » est parfois employé.

Du fait de ces propriétés, les matrices MDS sont au cœur de la conception ou de l'analyse des algorithmes modernes de chiffrement par bloc, dont AES, SHARKcite-ref-5[5], Square, Twofishcite-ref-6[6], Anubis, KHAZAD, Manta, Hierocrypt, Kalyna et Camellia. Les matrices MDS interviennent également, quoique de manière moins systématique, dans le design de certains algorithmes de hachage (par exemple Whirlpool).

• Définition

• Construction

• À partir de codes MDS

• Recherche exhaustive

• Applications

• Notes et références

• Notes

• Références

Soit K = F q {\displaystyle K=\mathbb {F} _{q}} un corps fini, et M {\displaystyle M} une matrice k × × k {\displaystyle k\times k} à coefficients dans K {\displaystyle K} . On dit que M {\displaystyle M} est une « matrice (de diffusion) MDS » si le code de matrice génératrice ( I k | M ) {\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}} , où I k {\displaystyle I_{k}} est la matrice identité, est un code MDScite-ref-7[Note 1]. Il existe plusieurs définitions équivalentes, qui peuvent être utilisées pour construire de telles matrices explicitement (voir ci-dessous) ; notamment, une matrice est MDS si et seulement si tous ses mineurs sont inversibles.

Par extension, on appelle encore matrice MDS les matrices binaires obtenues via une réalisation du corps K {\displaystyle K} sur le corps F 2 {\displaystyle \mathbb {F} _{2}} .

Une méthode courante pour construire des matrices MDS consiste à générer un code de Reed-Solomon sur F 2 m {\displaystyle \mathbb {F} _{2^{m}}} , puis mettre sa matrice génératrice sous forme systématique ( I k | M ) {\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}} .

Prenons par exemple K = F 8 ≃ ≃ F 2 [ X ] / ( X 3 + X + 1 ) {\displaystyle K=\mathbb {F} _{8}\simeq \mathbb {F} _{2}[X]/(X^{3}+X+1)} et construisons sur K {\displaystyle K} un code de Reed-Solomon de paramères [6, 3, 4], alors on obtient la matrice génératrice sous forme systématique ( I 3 | M ) {\displaystyle {\begin{pmatrix}I_{3}|M\end{pmatrix}}} avec

M = ( 1 X X 3 1 X 6 X 6 1 X 4 X 5 ) {\displaystyle M={\begin{pmatrix}1&X&X^{3}\\1&X^{6}&X^{6}\\1&X^{4}&X^{5}\end{pmatrix}}}

On peut obtenir à partir de M {\displaystyle M} une matrice binaire en remplaçant chaque X m {\displaystyle X^{m}} par la puissance correspondante de la matrice compagnon du polynôme X 3 + X + 1 {\displaystyle X^{3}+X+1} , on obtient alors

M b = ( 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 ) {\displaystyle M_{b}={\begin{pmatrix}{\begin{array}{c|c|c}{\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&0\\0&0&1\\1&1&1\end{array}}&{\begin{array}{ccc}1&1&0\\0&1&1\\1&1&1\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&1\\1&1&1\\1&0&1\end{array}}&{\begin{array}{ccc}1&1&1\\1&0&1\\1&0&0\end{array}}\end{array}}\end{pmatrix}}} Utiliser une représentation différente de F 8 {\displaystyle \mathbb {F} _{8}} donnerait des matrices M {\displaystyle M} et M b {\displaystyle M_{b}} différentes et non isomorphes.

Toutes les matrices MDS ne découlent pas de la construction ci-dessus. En particulier, il peut être souhaitable de doter la matrice de propriétés supplémentaires (qu'elle soit circulante, par exemple, afin d'en simplifier l'implémentation). Dans ces cas, il n'est pas rare de procéder à une recherche exhaustivecite-ref-8[7]cite-ref-9[8]cite-ref-10[9].

Les matrices MDS sont de bonnes matrices de diffusion et sont utilisées à cette fin dans les algorithmes de chiffrement par bloc. Ainsi, l'étape MixColumns de l'AES/Rijndael peut être vu comme la multiplication par une matrice MDS circulante, à savoir

M = ( 2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2 ) {\displaystyle M={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}}

où les coefficients appartiennent au corps fini AES isomorphe à F 256 {\displaystyle \mathbb {F} _{256}} . Cette matrice est un élément clé dans la stratégie de conception de l'AES, dite « wide trail » cite-ref-11[10]cite-ref-12[11].

cite-note-7Note 1. ↑ C'est-à-dire qu'il atteint la borne de Singleton.

cite-note-11. ↑ el-amrani2016nora-el-amrani2016Nora El Amrani, Codes additifs et matrices MDS pour la cryptographie, Université de Limoges, 24 février 2016 (lire en ligne)

cite-note-22. ↑ heystavares1994h-m-heyss-e-tavares1994(en) H. M. Heys et S. E. Tavares, « The design of substitution-permutation networks resistant to differential and linear cryptanalysis », CCS '94 Proceedings of the 2nd ACM Conference on Computer and communications security, ACM,‎ 2 novembre 1994, p. 148–155 (ISBN 0897917324, DOI 10.1145/191177.191206, lire en ligne, consulté le 11 août 2018)

cite-note-33. ↑ heystavares1995h-m-heyss-e-tavares1995(en) H.M. Heys et S.E. Tavares, « Avalanche characteristics of substitution-permutation encryption networks », IEEE Transactions on Computers, vol. 44, no 9,‎ 1995, p. 1131–1139 (ISSN 0018-9340, DOI 10.1109/12.464391, lire en ligne, consulté le 11 août 2018)

cite-note-44. ↑ canteautrou-2015anne-canteautjo-lle-rou-2015(en) Anne Canteaut et Joëlle Roué, « Differential Attacks Against SPN: A Thorough Analysis », dans Lecture Notes in Computer Science, Springer International Publishing, 2015 (ISBN 9783319186801, DOI 10.1007/978-3-319-18681-8_4, lire en ligne), p. 45–62

cite-note-55. ↑ rijmendaemenpreneelbosselaers1996vincent-rijmenjoan-daemenbart-preneelantoon-bosselaers1996(en) Vincent Rijmen, Joan Daemen, Bart Preneel et Antoon Bosselaers, « The cipher SHARK », dans Fast Software Encryption, Springer Berlin Heidelberg, 1996 (ISBN 9783540608653, DOI 10.1007/3-540-60865-6_47, lire en ligne), p. 99–111

cite-note-66. ↑ schneier-john-kelsey-doug-whiting-david-wagner-chris-hall-et-niels-ferguson1998bruce-schneier-john-kelsey-doug-whiting-david-wagner-chris-hall-et-niels-ferguson1998(en) Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall et Niels Ferguson, « Twofish: A 128-Bit Block Cipher - Schneier on Security », sur www.schneier.com, 15 juin 1998 (consulté le 10 août 2018)

cite-note-87. ↑ augotfiniasz2013daniel-augotmatthieu-finiasz2013(en) Daniel Augot et Matthieu Finiasz, « Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions », 2013 IEEE International Symposium on Information Theory, IEEE,‎ juillet 2013 (ISBN 9781479904464, DOI 10.1109/isit.2013.6620487, lire en ligne, consulté le 11 août 2018)

cite-note-98. ↑ simkhoooggierpeyrin2015siang-meng-simkhoongming-khoofr-d-rique-oggierthomas-peyrin2015(en) Siang Meng Sim, Khoongming Khoo, Frédérique Oggier et Thomas Peyrin, « Lightweight MDS Involution Matrices », dans Fast Software Encryption, Springer Berlin Heidelberg, 2015 (ISBN 9783662481158, DOI 10.1007/978-3-662-48116-5_23, lire en ligne), p. 471–493

cite-note-109. ↑ guptapandeyvenkateswarlu2016kishan-chand-guptasumit-kumar-pandeyayineedi-venkateswarlu2016(en) Kishan Chand Gupta, Sumit Kumar Pandey et Ayineedi Venkateswarlu, « On the direct construction of recursive MDS matrices », Designs, Codes and Cryptography, vol. 82, nos 1-2,‎ 14 juin 2016, p. 77–94 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-016-0233-4, lire en ligne, consulté le 11 août 2018)

cite-note-1110. ↑ daemenrijmen2002joan-daemenvincent-rijmen2002(en) Joan Daemen et Vincent Rijmen, « Security of a Wide Trail Design », dans Progress in Cryptology — INDOCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540002635, DOI 10.1007/3-540-36231-2_1, lire en ligne), p. 1–11

cite-note-1211. ↑ cid-sean-murphy-et-matthew-robshaw2006carlos-cid-sean-murphy-et-matthew-robshaw2006(en) Carlos Cid, Sean Murphy et Matthew Robshaw, Algebraic Aspects of the Advanced Encryption Standard, 2006 (DOI 10.1007/978-0-387-36842-9, lire en ligne)

• Portail de la cryptologie

• Portail des mathématiques